package com.xjl.everyinterview.datastructureandalgorithm.datastructure.binarytree;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Stack;

/**
 * @author xjl
 * @version 1.0
 * @description: 二叉树测试
 * @date 2021/8/16 19:21
 */
public class BinaryTest {

    public static void main(String[] args) {
        LinkedList<Integer> objects = new LinkedList<Integer>(Arrays.asList(new Integer[]{3, 2, 9, null, null, 10, null, null, 8, null, 4}));
//        for (int i = 0; i < 4; i++) {
//            Object o = objects.removeFirst();
//            System.out.println(String.valueOf(o));
//        }
        BinaryTreeI binaryTreeI = new RecursionBinaryTreeImpl();
        TreeNode binaryTree = binaryTreeI.createBinaryTree(objects);
        System.out.println(binaryTree);
        binaryTreeI.inOrderTraveral(binaryTree);

    }

    /**
     * 二叉树非递归前序遍历
     * @param node
     */
    public static void preOrderTraveralWithStack(TreeNode node) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode treeNode = node;
        while (treeNode != null || !stack.isEmpty()) {
            //迭代访问节点的左孩子，并入栈
            while (treeNode != null) {
                System.out.print(treeNode.data + " ");
                stack.push(treeNode);
                treeNode = treeNode.leftNode;
            }
            //如果节点没有左孩子，则弹出栈顶节点，访问节点右孩子
            if (!stack.isEmpty()) {
                treeNode = stack.pop();
                treeNode = treeNode.rightNode;
            }
        }
    }

}
